package paixu;

/**
 * @author lj
 * @Description: 快排
 * @date 2020-11-01 13:23
 * @QQ 851477108
 */


public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {5,8,6,2,4,3};
        quickSort(arr);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }

    /**
     * 快速排序，使得整数数组 arr 有序
     */
    private static void quickSort(int[] arr) {
        if (arr == null||arr.length < 2){
            return;
        }

        quickSort(arr,0,arr.length-1);
    }

    /**
     * 快速排序，使得整数数组 arr 的 [L, R] 部分有序
     */
    public static void quickSort(int[] arr,int l,int r){
        //不要忘了l<r前提条件
        if (l<r){
            //让数组把r位置的数与随机位置的数交换,可以不需要
            // 把数组中随机的一个元素与最后一个元素交换，这样以最后一个元素作为基准值实际上就是以数组中随机的一个元素作为基准值
//            swap(arr,l+(int)(Math.random()*(r-l+1)),r);

            //partition函数将arr数组[l,r]交换数据位置使部分有序，返回部分的第一个元素的下标和最后一个下标组成的整数数组
            int[] p = partition(arr,l,r);
            //子 过程左部分中开始递归，使其有序
            quickSort(arr,l,p[0]);
            //子过程右部分开始递归，使其有序
            quickSort(arr,p[1],r);
        }
    }

    /**
     * 分区的过程，整数数组 arr 的[L, R]部分上，使得：
     *   大于 arr[R] 的元素位于[L, R]部分的右边，但这部分数据不一定有序
     *   小于 arr[R] 的元素位于[L, R]部分的左边，但这部分数据不一定有序
     *   等于 arr[R] 的元素位于[L, R]部分的中间
     * 返回等于部分的第一个元素的下标和最后一个下标组成的整数数组
     */
    public static int[] partition(int[] arr, int l , int r){
        int less = l-1;
        int more = r+1;
        int num = arr[r];
        //将数组内位置交换，直到确认num左小右大
        while (l<more){
            if (arr[l]<num){
                //如果arr[l]小于num,从最左交换arr[l],l++
                swap(arr, ++less, l++);
            }else if (arr[l]>num){
                //如果arr[l]大于num,从最右交换arr[l]
                swap(arr, --more,l);
            }else {
                //如果arr[l]等于num，l++
                l++;
            }
        }
        //找到num左小右大的位置more,交换arr[more]和arr[r]
        swap(arr,more,r);
        return new int[] {less,more};
    }

    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
